<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>优先队列</title>
</head>
<body>
<p>认队列也有一些修改版本。其中一个修改版就是优先队列。</p>
<p>元素的添加和移除是基于优先级的。一个现实的例子就是机场登机的顺序。<br>
    头等舱和商务舱乘客的优先级要高于经济舱乘客。<br>
    在有些国家，老年人和孕妇（或带小孩的妇女）登机时也享有高于其他乘客的优先级。</p>
<p>实现一个优先队列，有两种选项：设置优先级，然后在正确的位置添加元素；<br>
    或者用入列操作添加元素，然后按照优先级移除它们。</p>
<script type="text/javascript">
    /***********************************************************************************************************/
    // 在这个示例中，我们将会在正确的位置添加元素，因此可以对它们使用默认的出列操作：
    function PriorityQueue() {
        let items = [];

        function QueueElement(element, priority) { // {1}
            this.element = element;
            this.priority = priority;
        }

        this.enqueue = function (element, priority) {
            let queueElement = new QueueElement(element, priority);
            let added = false;
            for (let i = 0; i < items.length; i++) {
                if (queueElement.priority < items[i].priority) { // {2}
                    items.splice(i, 0, queueElement); // {3}
                    added = true;
                    break; // {4}
                }
            }
            if (!added) {
                items.push(queueElement); //{5}
            }
        };
        this.print = function () {
            for (let i = 0; i < items.length; i++) {
                console.log(`${items[i].element}- ${items[i].priority}`);
            }
        };
        //其他方法和默认的Queue实现相同
    }

    /**
     * 默认的Queue类和PriorityQueue类实现上的区别是，要向PriorityQueue添加元素，需
     * 要创建一个特殊的元素（行{1}）。这个元素包含了要添加到队列的元素（它可以是任意类型）
     * 及其在队列中的优先级。
     *
     * 如果队列为空，可以直接将元素入列（行{2}）。否则，就需要比较该元素与其他元素的优
     * 先级。当找到一个比要添加的元素的priority值更大（优先级更低）的项时，就把新元素插入
     * 到它之前（根据这个逻辑，对于其他优先级相同，但是先添加到队列的元素，我们同样遵循先进
     * 先出的原则）。要做到这一点，我们可以用第2章学习过的JavaScript的array类的splice方法。
     * 一旦找到priority值更大的元素，就插入新元素（行{3}）并终止队列循环（行{4}）。这样，
     * 队列也就根据优先级排序了。
     *
     * 如果要添加元素的priority值大于任何已有的元素，把它添加到队列的末尾就行了（行{5}）
     * **/
    let priorityQueue = new PriorityQueue();
    priorityQueue.enqueue("John", 2);
    priorityQueue.enqueue("Jack", 1);
    priorityQueue.enqueue("Camila", 1);
    priorityQueue.print();

    /***********************************************************************************************************/
</script>
</body>
</html>
